package chart.图的遍历;

import chart.图的存储.AbstractGraph;
import chart.图的存储.AdjacencyMatrix;
import chart.图的存储.AdjacencyTable;
import chart.图的存储.Edge;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 广度优先搜索
 * <p>相当于树的层序遍历</p>
 * <p>可以判断图是否有环</p>
 * <p>算法要点：</p>
 * <p>遍历非连通图, 通过一个 bool 数组记录顶点是否被访问过, 除了遍历非连通图外, 也可以防止图有环而导致死循环</p>
 * <p>队列存储顶点</p>
 * <p>遍历非连通图, 通过一个 bool 数组记录顶点是否被访问过</p>
 *
 * <p>空间复杂度: O(V)</p>
 * @author yezh
 * @date 2023/7/11 18:54
 */
public class GraphBFS {

    public static void main(String[] args) {
        testAdjacencyMatrix();
        System.out.println();
        testAdjacencyTable();
    }

    private static void testAdjacencyMatrix() {
        // 时间复杂度: O(V * V), 需要遍历整个矩阵
        AbstractGraph graph = new AdjacencyMatrix(6, false);
        graph.createGraph(Edge.graphDFS());
        bfs(graph);
    }

    private static void testAdjacencyTable() {
        // 时间复杂度: O(V + E), 需要遍历顶点和边
        AbstractGraph graph = new AdjacencyTable(6, false);
        graph.createGraph(Edge.graphDFS());
        bfs(graph);
    }

    public static void bfs(AbstractGraph graph) {
        int n = graph.getV();
        boolean[] visited = new boolean[n];
        Deque<Integer> queue = new ArrayDeque<>(graph.getV());
        for (int vertex = 0; vertex < n; vertex++) if (!visited[vertex]) bfs(vertex, visited, queue, graph);
    }

    private static void bfs(int vertex, boolean[] visited, Deque<Integer> queue, AbstractGraph graph) {
        visit(vertex);
        queue.offer(vertex);
        visited[vertex] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                vertex = queue.poll();
                for (Integer neighborVertex : graph.getNeighborVertex(vertex))
                    if (!visited[neighborVertex]) {
                        visit(neighborVertex);
                        queue.offer(neighborVertex);
                        visited[neighborVertex] = true;
                    }
            }
        }
    }

    private static void visit(int vertex) {
        System.out.print(vertex + " ");
    }

}
